二次扫描与换根法模板题；

f[x]=f[y]-size[x]+n-size[x]

记得开long long

推P2986，与此题思路相似

#include <bits/stdc++.h>
#define INF 0x3F3F3F3F3F3F3F3F
#define N 1000100
using namespace std;
typedef long long ll;

vector<ll> a[N];
ll n, u, v;
ll dep[N];  //由1开始的节点深度
ll size[N]; //由1开始形成的一棵树，这个树每个点的子节点数量
ll f[N];
ll ansx = -INF;
ll ansn;

void dfs(ll x, ll fa)
{
    dep[x] = dep[fa] + 1;
    size[x] = 1;
    for (ll i = 0; i < a[x].size(); i++)
    {
        ll y = a[x][i];
        if (fa == y)
            continue;
        dfs(y, x);
        size[x] += size[y];
    }
}

void dp(ll x, ll fa)
{
    for (ll i = 0; i < a[x].size(); i++)
    {
        ll y = a[x][i];
        if (y == fa)
            continue;
        f[y] = f[x] - size[y] + (n - size[y]); //y节点下的子节点深度全部-1，所以-size[y],除y节点以及其子节点以外的节点深度全部+1，即+(n-size[y])..
        dp(y, x);
    }
}

int main()
{
    scanf("%d", &n);
    for (ll i = 1; i <= n - 1; i++)
    {
        scanf("%lld%lld", &u, &v);
        a[u].push_back(v);
        a[v].push_back(u);
    }
    dfs(1, 0);
    for (ll i = 1; i <= n; i++)
        f[1] += dep[i];
    dp(1, 0); //转移
    for (ll i = 1; i <= n; i++)
    {
        if (ansx < f[i])
        {

            if (ansx != f[i])
                ansx = f[i], ansn = i;
            else
                ansn = min(ansn, i);
        }
    }
    cout << ansn;
    return 0;
    //printf("%lld",ansx);
}